'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-11-25 09:40:25
'''
#
# @lc app=leetcode.cn id=1370 lang=python3
#
# [1370] 上升下降字符串
#

# @lc code=start
class Solution:
    def sortString(self, s: str) -> str:
        import collections
        store=collections.defaultdict(lambda:0)
        for i in s:
            store[i]+=1
        ss=list(set(s))
        ss.sort()
        ans=''
        while len(ans)<len(s):
            for i in ss:
                if store[i]>0:
                    ans+=i
                    store[i]-=1
            for i in ss[::-1]:
                if store[i]>0:
                    ans+=i
                    store[i]-=1
        return ans
        
# @lc code=end

